package org.example.code.test2024.nine_mouth;

import org.example.code.test2024.eight_mouth.TreeNode;

import java.util.*;


public class test0902 {
    int sum = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        sum = 1;
        depth(root);
        return sum;
    }

    private int depth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        int ans = Math.max(left,right)+1;
        sum = Math.max(sum,ans);
        return ans;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue = new PriorityQueue<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode poll = queue.poll();
                item.add(poll.val);
                if(poll.left!=null){
                    queue.offer(poll.left);
                }
                if(poll.right!=null){
                    queue.offer(poll.right);
                }
            }
            list.add(item);
        }
        return list;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return fun(nums,0,nums.length-1);
    }

    private TreeNode fun(int[] nums, int l, int r) {
        if(l>r)
            return null;
        int mid = (l+r+1)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = fun(nums,l,mid-1);
        node.right = fun(nums,mid+1,r);
        return node;
    }

    public boolean isValidBST(TreeNode root) {
        return checkIsValidBST(root,Long.MAX_VALUE,Long.MIN_VALUE);
    }

    private boolean checkIsValidBST(TreeNode root, long maxValue, long minValue) {
        if(root==null){
            return true;
        }
        if(root.val>maxValue||root.val<minValue){
            return false;
        }
        return checkIsValidBST(root.left, root.val,minValue)&&checkIsValidBST(root.right,maxValue,root.val);
    }


    public int kthSmallest(TreeNode root, int k) {
        List<TreeNode> list = new ArrayList<>();
        getListByBST(root,list);
        return list.get(k-1).val;
    }

    private void getListByBST(TreeNode root, List<TreeNode> list) {
        if(root==null){
            return;
        }
        getListByBST(root.left,list);
        list.add(root);
        getListByBST(root.right,list);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode poll = queue.poll();
                item.add(poll.val);
                if(poll.left!=null){
                    queue.offer(poll.left);
                }
                if(poll.right!=null){
                    queue.offer(poll.right);
                }
            }
            list.add(item.get(item.size()-1));
        }
        return list;
    }


    public void flatten(TreeNode root) {

    }

}
